package 牛客网在线编程题库;

/**
 * 题目描述
 给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针
 例如，
 给出的链表为: 1->2->3->4->5,n=2
 删除了链表的倒数第 n 个节点之后,链表变为1->2->3->5

 备注：
 题目保证 nn 一定是有效的
 请给出请给出时间复杂度为O(n) 的算法
 示例1
 输入
 {1,2},2
 返回值
 {2}
 */

public class _删除链表的倒数第n个结点 {
    public static void main(String[] args) {

    }

    /**
     * 需要考虑多种情况，谨记
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd (ListNode head, int n) {
        // 校验合法性
        if (head == null) {
            return null;
        }
        // 定义链表长度
        int len = 1;
        // 定义遍历指针
        ListNode cur = head;
        // 遍历求链表长度
        while (cur.next != null) {
            // 长度自增
            len++;
            // 指针后移
            cur = cur.next;
        }
        // 若链表等于n
        if (len == n) {
            return head.next;
        }
        // 定义二次遍历指针
        ListNode temp = head;
        // 遍历到要删除结点的前一个结点
        for (int i = 0 ; i < len - n - 1 ; i++) {
            temp = temp.next;
        }
        // 若直接删除倒数第一个(也即最后一个)，将倒数第二个结点的下一个结点直接置空即可
        if (n == 1) {
            temp.next = null;
        }else {
            // 若不是删除最后一个，则将被删除结点的前一个结点指向被删除结点的下一个结点即可
            temp.next = temp.next.next;
        }
        return head;
    }
}
